package com.heima.leetcode.practice;

import java.util.HashMap;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 138. 复制带随机指针的链表
 * @date 2025/6/5 11:22
 */
public class E138 {

    public static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    /**
     * 暂存
     */
    private final HashMap<Node, Node> map = new HashMap<>();

    /**
     * 思路：先处理next指针后处理random指针，结合哈希表
     *
     * @param head 头节点
     * @return 拷贝后的链表头节点
     */
    public Node copyRandomList(Node head) {
        Node sentinel = new Node(-1), curr = sentinel, p = head;
        while (p != null) {
            Node node = new Node(p.val);
            map.put(p, node);
            curr.next = node;
            curr = curr.next;
            p = p.next;
        }
        curr = sentinel.next;
        p = head;
        while (p != null) {
            curr.random = map.get(p.random);
            curr = curr.next;
            p = p.next;
        }
        return sentinel.next;
    }
}
